/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package a2;

import java.lang.String;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Set;
import org.jgrapht.graph.DefaultWeightedEdge;
import org.jgrapht.graph.SimpleDirectedWeightedGraph;

/**
 *
 * @author abd920
 */
public class Dijkstra implements Algorithm {

    List<Knoten> tab = null;//Liste der Knoten -> Tabelle auf der man arbeitet
    List<String> erg = null;//kürzester weg
	int counter = 0;// zugriffscounter

	private void resetLists() {//resetet die Listen, damit keine Seiteneffekte auftreten, da noch ergebnisse anderer durchläufe drin sind
		tab = new ArrayList<Knoten>();
		erg = new ArrayList<String>();
	}
	
    private void addToList(Knoten knot) {//die tabelle bekommt einen knoten
        tab.add(knot);
    }

    private void deleteFromList(Knoten knot) {//löschen eines knotens aus der tabelle
        for (Knoten x : tab) {
            if (x == knot) {
                tab.remove(x);
            }
        }
    }
    
    private Knoten findNode(String name) {//läuft solange durch die tabelle bis er den knoten mit namen string findet
        for (Knoten x : tab) {
            if (x.name.equals(name))
                return x;
        }
        return null;
    }
    
    
    private Knoten nextNode() {
        Knoten next = null;
        for (Knoten k : tab) {//läuft die knoten ab
            if (next == null) {//erster fall
              if (k.ok == false)//der knoten wurde noch nicht angefasst
                  next = k;//k wird nächster knoten
            } else {
                if (k.ok == false && k.entf < next.entf)//wenn k noch nicht angefasst wurde und die entfernung kürzer ist, als der bisher kürzeste
                    next = k;
            }
        }
        return next;
    }

    private boolean finished() {//finished wenn alle angefasst wurden, sonst false
        for (Knoten k : tab) {
            if (k.ok == false) {
                return false;
            }
        }
        return true;
    }

    @Override
    public List<String> getShortestWay(SimpleDirectedWeightedGraph<String, DefaultWeightedEdge> graph, String source, String target) {
        resetLists();
		counter = 0;
		//wenn start oder ziel nicht innerhalb des graphen sind
        if (!graph.containsVertex(source) || !graph.containsVertex(target)) {
            return null;
        }
        for (String x : graph.vertexSet()) {//legt den startknoten an(in tab)
            if (source.equals(x)) {
                Knoten start = new Knoten(x);
                start.vorg = x;
                start.entf = 0;
                start.ok = false;
                addToList(start);
            } else {// legt alle nicht startknoten an(in tab)
                addToList(new Knoten(x));
            }
        }

        while (!finished()) {// solange nicht alle angefasst wurden
            Knoten current = nextNode();//nimm den nächsten nicht angefassten knoten
            current.ok = true;//setze ok auf true
            Set<DefaultWeightedEdge> outgoing = graph.outgoingEdgesOf(current.name);//nimm alle kanten die von current weggehen
			counter++;//zugriff++
            for (DefaultWeightedEdge x : outgoing) {//für alle die von current weggehen
                Knoten k = findNode(graph.getEdgeTarget(x));
                double edgeWei = graph.getEdgeWeight(x);
				counter++;
                if (k.ok == false) {//wenn der wegehende noch nicht angefasst wurde
                    if (k.entf > current.entf + edgeWei) {//wenn der weg von start zu current kürzer ist als bereits vorher abgelaufener
                        k.entf = current.entf + edgeWei;//setze diesen kürzeren weg
                        k.vorg = current.name;//neuer vorgänger mit kürzerem weg
                    }
                }
            }
        }
        
        List<String> result = new ArrayList<String>();//ergebnis liste
        Knoten ziel = findNode(target);//finde ziel
        if(ziel.vorg == null){//nur wenn zeil nicht im graphen ist relevant-> leere liste
            return result;
        }
        
        while(ziel.vorg != null && !source.equals(ziel.name)){//normaler graph
            result.add(ziel.name);//add ziel
            ziel = findNode(ziel.vorg);//hangele dich an den vorgängern zum start
        }
        result.add(source);// add start
        Collections.reverse(result);//reverse
        return result;//...
    }

    @Override
    public int getLastAccessCount() {//gitb die anzahl der zugriffe zurück
		return counter;
    }

    private class Knoten {//die knoten die die tabelle darstellen

        String name;
        String vorg = null;
        boolean ok = false;
        double entf = Double.POSITIVE_INFINITY;

        Knoten(String name) {
            this.name = name;
        }
    }
}
